This invention relates to embedded coders and more particularly to an embedded image encoder with improved compression efficiency and decreased implementation complexity.
The ability to adjust the compression ratio by simply truncating an encoded bitstream makes embedded coding attractive for a number of applications such as progressive image transmission, internet browsing, scalable image and video databases, digital cameras, low delay image communications, etc. Taking Internet image browsing as an example, embedded coding makes it feasible to store only one copy of a high quality compressed bitstream on the server.
Depending on user demand, channel bandwidth conditions, and browser monitor quality, selectable amounts of the compressed bitstream are delivered to the browser. At an early stage of browsing, images can be retrieved with coarse quality so that a user can quickly go through a large number of images before choosing one of interest. The chosen image is then fully downloaded with a much better quality level. During the download process, the image quality is incrementally refined. The user can cancel the download process as soon as the quality is satisfactory.
Shapiro describes an Embedded Zerotree Wavelet algorithm (EZW) in his paper J. M. Shapiro, xe2x80x9cEmbedded Image Coding Using Zerotrees of Wavelet Coefficients,xe2x80x9d IEEE Trans. on Signal Processing, Vol. 41, No. 12, pp. 3445-3462, December 1993. The embedded image coded bitstream can be terminated or truncated at any point. This allows the decoded image to always have a reasonable good quality with respect to the number of coded bits actually used. The zero tree symbol contains coefficients across multiple subbands. Therefore, in implementation, the coder has to traverse multiple subbands to establish the zero tree structure, the memory requirement of the codec is thus high. Furthermore, the cross subband zerotree symbol also makes it inefficient for spatial scalable image coding, i.e., to decode only an image of a coarser resolution.
New improvements over the EZW include the Set Partitioning in Hierarchical Trees (SPIHT) encoding algorithm described by Said and Pearlman. A. Said and W. Pearlman, xe2x80x9cA New, Fast, and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees,xe2x80x9d IEEE Trans. on Circuits and Systems for Video Technology, Vol. 6, No. 3, pp. 243-250, June 1996. SPIHT maintains and manipulates 3 lists during coding: the list of insignificant sets (LIS), the list of insignificant pixels (LIP) and the list of significant pixels (LSP). With arithmetic entropy coding, SPIHT outperforms EZW. Furthermore, one mode of SPIHT achieves good compression efficiency without using any explicit Variable Length Code (VLC) such as a Huffman code or arithmetic code. However, at high bit-rates, the list built by SPIHT becomes very large and memory consuming. Therefore, it is expensive to implement.
Chui and Yi proposed a nested split coding algorithm. C. Chui, R. Yi, xe2x80x9cSystem and method for nested split coding of sparse data setsxe2x80x9d, U.S. Pat. No. 5,748,116. The nested coding encodes transform coefficients in data blocks. The algorithm is very fast and cheap to implement, but does not have the embedded functionality which is crucial in many applications.
A need remains for further improving the compression efficiency and reducing the implementation complexity of encoding techniques such as EWZ and SPIHT.
A quad-tree embedded image coding technique is used in combination with a bit-plane encoding technique to provide an efficient and low complexity embedded image coding system. A simple quad-tree method identifies transform coefficients as significant, insignificant, or refinement at each successive quantization level. The quad-tree technique is used instead of the zero-tree or hierarchical tree used in previous encoders. Since the quad-tree can be restricted within the subband, it may achieve spatial scalability in additional to the quality scalability. The coder does not maintain a list in coding, which also decrease the memory requirement for the coder.
The quad-tree embedded encoder takes as input a two-dimensional array of image coefficients, with each coefficient having values extending over multiple bit-planes. The coefficients are segmented into a certain number of root blocks. The segmentation can be just one root block covering the entire image, or it can be pre-split subbands where one subband is an initial root block, or it can be a number of pre-specified blocks covering the entire image. A block is said to be significant if and only if there is any xe2x80x9c1xe2x80x9d bit in the current bit-plane or in the more significant bit-plane of the block. The encoder proceeds bit-plane by bit-plane, from the most significant bit-plane to the least significant bit-plane. For each bit-plane, the encoder checks each root block for one of three cases.
In the first case the block was already significant at the previous bit-plane, the encoder then proceeds to each of its four sub-blocks (quadrants). In the second case the block just becomes significant at the current bit-plane, a xe2x80x9c1xe2x80x9d bit is encoded and the encoder proceeds to each quadrant of the block. In the third case the block remains insignificant, a xe2x80x9c0xe2x80x9d bit is encoded concluding coding of the block for the current bit-plane.
If the encoder proceeds to each quadrant, it repeats the same operations on each sub-block (quadrant). The quadrant significance information may be optionally entropy encoded by a Huffman or arithmetic coder, or may be simply directly sent into the bitstream.
Once a split quadrant reaches the size of a single coefficient, the bit of the current coefficient at the current bit-plane is encoded, and if the coefficient just becomes significant, its sign bit is encoded right after. The coding and splitting of quadrants is repeated for each progressively lesser significant bit-plane until reaching a predetermined number of encoded bits or image quality.
The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment of the invention which proceeds with reference to the accompanying drawings.